package OfferOneHundred;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-06-30 12:44
 * @description: LeetcodeLearnAlgorithm -> OfferOneHundred
 */
public class Q4二维数组中的查找 {
    public static void main(String[] args) {
        Q4二维数组中的查找 test = new Q4二维数组中的查找();
        int[][] matrix = {
                {1,   4,  7, 11, 15},
                {2,   5,  8, 12, 19},
                {3,   6,  9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30},
        };
        int[][] matrix2 = {
                {-1},
                {-1}
        };
        int[][] matrix3 = {
                {5},
                {6}
        };
        // System.out.println(test.findNumberIn2DArray(matrix,5));
        // System.out.println(test.findNumberIn2DArray(matrix,20));
        // System.out.println(test.findNumberIn2DArray(matrix2,-2));
        System.out.println(test.findNumberIn2DArray(matrix3,6));

    }

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int col = 0;
        for (int row = 0; row < matrix.length; row++) {
            for (; col < matrix[0].length; col++) {
                if (matrix[row][col] < target) {
                    continue;
                } else if (matrix[row][col] > target){
                    if (col == 0) {
                        return false;
                    }
                    // col--;
                    while (matrix[row][col] > target) {
                        if (col > 0) {
                            col--;
                        } else {
                            return false;
                        }

                        if (matrix[row][col] == target) {
                            return true;
                        }
                    }
                    break;
                } else if (matrix[row][col] == target) {
                    return true;
                }
            }
            if (col == matrix[0].length) {// && matrix[0].length != 1
                col--;
            }
        }
        return false;
    }
}
